1. Field of the Invention
The present invention relates to a novel infrastructure and method to seamlessly integrate logic synthesis and physical placement through a transformational approach, and more specifically to a method and apparatus for applying fine-grained transformations during placement synthesis interaction.
2. Description of the Related Art
Typically, in chip design, several steps are performed in sequence including a high level synthesis step for creating a register transfer level representation of the design, a logic synthesis step for automatically creating a circuit from the register transfer level description, a placement step to place the circuits on the chip, a routing step for routing the placed design and finally fabrication can be performed. Traditionally, logic synthesis and placement have been two separate steps.
Recently, attempts to combine these two design steps (logic synthesis and placement) have been made. However, performing these steps in combination (at the same time) is problematic. That is, it is difficult to design the logic since it is unknown where the circuit will be placed on the wafer, and hence connection is uncertain. For example, the length of the wires is not known and thus the logic design cannot be performed with certainty. Thus, many assumptions must be made which are typically incorrect.
Further, timing optimization in traditional logic synthesis is based on a transformational approach. A netlist (an interconnected schematic of gates) is gradually modified and refined. Timing, noise and power analyzers incrementally measure the design and provide feedback to the transforms (e.g., algorithms) that make the actual design changes (e.g., see Stok et al., “Booledozer: logic synthesis for asics, IBM Journal of Research and Development (July 1996)). For example, the timing analyzer analyzes the timing of the proposed circuits placed on the chip. An evaluator (or the transform itself) queries the analyzers and decides if the design actually improves and accepts/rejects the netlist modifications based on whether the design is improved.
The advantage of the above approach is that direct feedback from the analyzer(s) is used in the synthesis optimizations. There is a direct coupling between the analyzers used for the final sign-off criteria and the optimization. This direct coupling allows discrete logic and electrical netlist optimizations within synthesis.
Algorithms for placement of circuits on the chip have the advantage of a rigid underlying mathematical formulation. They have been very successful in optimizing net length and controlling wire congestion and their complexities scale well to handle larger designs. Most placement algorithms use continuous formulations (i.e., the placement problem is formulated as a continuous mathematical optimization problem) and hence do not lend themselves to discrete optimizations (e.g., such as buffer insertion, pin swapping, etc.) typically used in synthesis.
Timing-driven placement techniques have often used the ability to specify constraints into the placement algorithm such as net weights and capacitance targets to achieve such goals (e.g., see Donath et al., “Timing driven placement using complete path delays”, In Proc. ACM/IEEE Design Automation Conference (June 1990), IEEE Computer Society Press); Sarrafzadeh et al., “Unification of budgeting and placement”, Proc. ACM/IEEE Design Automation Conference (1997), 758–761); and Kleinhans et al., “Gordian: VLSI placement by quadratic programming and slicing optimization”, IEEE Transactions on Computer-Aided Design (1991), 356–365). However, they do not directly take into account feedback from, for example, a timing analyzer because the placement problem is formulated with the objective of minimizing total wire length. These techniques formulate their problems as continuous optimization problems, and hence do not lend themselves easily to include netlist transformations which are discrete in nature (e.g., buffer insertion, remapping, pin swapping etc.).
Including these objectives directly in the problem formulation leads to expensive optimization algorithms. In Srinivasan et al., “RITUAL: A performance driven placement algorithm for small cell ICs”, In Proc. International Conf. Computer-Aided design (ICCAD) (November 1991), pp. 48–51), locations are specified as variables for timing improvement and an exact non-linear optimization problem is formulated to achieve this goal. However, the runtime of non-linear methods tends to grow quickly with the size of the designs.
A typical conventional approach has been to use a snapshot of placement as a starting point for netlist transformations, followed by an incremental placement step (e.g., see Kannan et al., “A methodology and algorithms for post-placement delay optimization”, In Proc. ACM/IEEE Design Automation Conference (June 1994), IEEE Press); Lee et al., “Incremental timing optimization for physical design by interacting logic restructuring and layout”, International Workshop in Logic Synthesis (1998), 508–513); Lou et al., “Exact solution to simultaneous technology mapping and linear placement problem”, Proc. International Conf. Computer-Aided Design (ICCAD) (1997)) and Murofushi et al., “Layout driven re-synthesis for low power consumption Isis”, In Proc. ACM/IEEE Design Automation Conference (June 1997), IEEE Press) to legalize the perturbations caused by the netlist transforms. These approaches significantly limit the netlist changes that can be made to be able to maintain incrementality in the succeeding placement.
In one approach referred to as “POINT” (e.g., see Stenz et al., “Timing driven placement in interaction with netlist transformations”, Proc. International Symposium on Physical Design (1997)), the approach is extended by adding a flow-based placement improvement phase as a legalization step, thereby increasing the number and scope of network changes that can be tolerated. In Hojat et al., “An integrated placement and synthesis approach for timing closure of PowerPC microprocessors”, Proc. International Conf. Computer Design (ICCD) (1997), pages 206, 210), a methodology that enables one to invoke synthesis transforms in the intermediate steps of a partitioning based placer is described.
All of these approaches start from an existing placement and only try to optimize around this initial local minimum.
FIG. 1 illustrates a three-axes graph which serves to describe how the traditional methods allow for placement synthesis integration. In FIG. 1, it is shown that as optimizations may be made in one domain, the other two domains will be affected. That is, the conventional methods looked at each domain in sequence, and not all at the same time. Thus, for example, typically first the boolean design will be optimized, then the electrical design will be optimized, and finally the placement of the circuit on the chip will be optimized. Such a sequential operation leads to inefficiency.
Hence, in FIG. 1, the three axes represent optimizations along boolean, electrical and physical domains. Each step (e.g., changes made in each domain) or algorithm moves the design from one point in the design space to another. In the traditional flows, netlist optimizations (such as cloning, buffer insertion, etc.) are alternated with placement steps (including techniques well known in the art such as min-cut partitioning, reflow, etc.)
Such steps are shown as AB, BC, CD, DE and EF. However, in this flow, numerous steps are required to go from point A to point F. The sequential optimization constrains the design to go from point A to point B, to point C etc. This constraining is forced on each of the tools since, for example, the boolean optimizer knows nothing of the electrical properties which the electrical optimizer must optimize, and the electrical optimizer knows nothing of the physical properties which the physical optimizer must optimize. In typical chip design methodologies, the logic synthesis and placement step are split into two parts. Hence, guesswork is involved.
Thus, no single step may optimize the physical, boolean and electrical dimensions, thus moving the design from point A to F in the design space. Further, a more optimal design point F′ is missed by the optimization process due to the inability to evaluate and optimize the three dimensions at once. Using the methods of the invention, one is able to evaluate various points including F′ directly. Thus, for example, in the conventional method, a remapping step where a complex gate is broken down into simpler gates will not optimize multiple objectives simultaneously (e.g., by choosing the physical locations of the simpler gates, the sizes and electrical gains of the chosen gates and the topology of boolean function, etc.).
Hence, the conventional methods are constrained by each step not knowing what the next step in the sequence is going to do.
In a first conventional method, nets are weighted during successive partitioning stages of placement. The goal is to use the electrical information by apportioning the slack weights according to the timing debt during the min-cut partitioning process. Logic design is performed during the intermediate stages of such a min-cut partitioning process.
However, this first method has placement and logic redesign which are alternate steps in an iteration. There is no consideration let alone recognition that a single fine grained step which may comprise of multiple objectives and constraints which involve both physical (placement), electrical and logical data, would be useful or efficient. Further, the logic redesign step is applied in a given “cut depth”. Thus, there is a distinction between a placement and synthesis step. Hence, in this method, no step may move the circuit from one design space (both physical and logical) to another.
Moreover, this first conventional method is unable to use a partially placed and synthesized design as the starting point. Hence, an incremental netlist and physical design improvement is not possible in this method. Additionally, in this first conventional method, the flow is not a single converging flow of successive application of fine grained steps. Instead, this method merely uses an iteration of partial placement and partial logic redesign steps. Finally, this first conventional method is not based on the infrastructure of bins, and therefore is unable to allow for quick logic redesign with placement. Moreover, there is no ability to externally control the logic/placement redesign using scenarios.
In a second conventional method, a layout of an integrated circuit design is provided, which includes placing cells, followed by verification of the timing in the layout area. If the timing does not verify, a means is provided for modifying the netlist and making an ECO change of the placement to reflect this new netlist followed by placement iteration. The second method is also directed to placement of results of the behavioral synthesis.
However, this second method is problematic in that there are no placement and netlist changes (synthesis) performed together in the form of fine-grained transforms. Moreover, there is no timing verification which is internal to both the placement and synthesis algorithms leading to a converging placement/netlist change flow. Moreover, the step of making netlist changes followed by ECO placement is inefficient and unnecessary.
In a third conventional method, a net weighting algorithm is provided to influence a min-cut-based placement program to meet timing and improve area and total wire length while performing placement. The key idea is to assign weights to critical nets based on the current timing violations and to non-critical nets based on the difference between the maximum allowed and the current estimated capacitances. Additionally, a propagation delay estimation technique is provided for the nets on the critical path, and a weighting technique of driver/buffer pairs is provided for ensuring that the most sensitive nets are kept short.
However, this third conventional method is deficient in that placement and netlist changes are not performed concurrently. Further, the placement program is not incremental in nature and there is no option, at every step, of intercepting the placement program and experimenting with a range of netlist change transforms (that are more effective than net weighting), for improving the design.
Finally, in a fourth conventional method, a timing slack graph is generated to provide communication between a placement tool and a timing constraint generator. The slack graph, used in conjunction with a timing calculator and a net bounding box model, converts timing constraints into placement constraints. Path timing constraints are concurrently handled by imposing physical constraints on the placement.
However, this fourth conventional method is problematic in that it performs only placement changes. Hence, timing is not constructively improved by concurrently applying both placement and netlist changes.
Thus, the conventional techniques have serious drawbacks which lead to inefficiency and complex, time-consuming computations and expenditure of system resources.